package 回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * 46.全排列
 *
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 * 全排列问题可以通过回溯算法来解决，核心思想是递归地选择未被使用的元素，直到形成一个完整的排列。以下是详细的解题思路和代码实现：
 *
 * 解题思路
 * 回溯法框架：使用递归函数进行深度优先搜索，通过回溯遍历所有可能的路径。
 * 路径记录：维护一个当前路径（path），记录已选择的元素。
 * 标记使用状态：使用布尔数组（used）标记元素是否已被使用，避免重复选择。
 * 终止条件：当路径长度等于原数组长度时，将当前路径添加到结果列表。
 * 递归与回溯：每次选择一个未被使用的元素，递归调用后撤销选择，进行下一轮尝试。
 */
public class L_46 {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(res,path,nums,used);
        return res;
    }

    /**
     * 递归求排列
     * @param res 结果值
     * @param path 当前递归值
     * @param nums 数组
     * @param used 标识数组中的元素是否被使用
     */
    private void backtrack(List<List<Integer>> res, List<Integer> path, int[] nums, boolean[] used){
        // 当路径长度等于数组长度时，将当前路径添加到结果列表
        if (path.size() == nums.length){
            res.add(new ArrayList<>(path)); // 注意创建新列表，避免引用问题
            return;
        }
        // 遍历所有元素，选择未被使用的元素
        for (int i = 0; i < nums.length; i++) {
            if (!used[i]){
                path.add(nums[i]); // 选择当前1元素
                used[i] = true; // 标记当前元素已使用
                backtrack(res, path, nums, used); // 进入下一层递归
                path.remove(path.size() - 1); // 回溯，撤销选择
                used[i] = false; // 回溯，恢复当前元素为未使用状态
            }
        }

    }
}
